#include <iostream>
#include <string.h>

using std::cout;
using std::endl;

template<typename T>
class Stack{
public:
    Stack():top_(-1), cap_(10), arr_(new T[cap_]){}
    ~Stack(){}

    void push(T data) 
    {
        if(top_ == cap_ - 1){
            expand();
        }
        arr_[++top_] = data;
    }

    bool empty() const
    {
        return top_ == -1;
    }

    T top() const
    {
        if(empty())
            throw "stack is empty()";

        return arr_[top_];
    }

    void pop()
    {
        if(empty())
            throw "stack is empty()";
        --top_;
    }

private:
    void expand()
    {
        cap_ = cap_ * 2;
        T *tmp = new T[cap_];
        memcpy(tmp, arr_, (top_ + 1) * sizeof(T));
        delete [] arr_;
        arr_ = tmp;
    }

private:
    int top_;
    size_t cap_;
    T *arr_;
};

template<typename T>
class Queue{
public:
    void push(T data)
    {
        fir_.push(data);
    }

    T top()
    {
        if(sec_.empty()){
            while(!fir_.empty()){
                T val = fir_.top();
                fir_.pop();
                sec_.push(val);
            }
        }

        return sec_.top();
    }

    void pop()
    {
        if(sec_.empty()){
            while(!fir_.empty()){
                T val = fir_.top();
                fir_.pop();
                sec_.push(val);
            }
        }


        sec_.pop();
    }

    bool empty()
    {
        return fir_.empty() && sec_.empty();
    }


    Queue(){}
    ~Queue(){}

private:
    Stack<T> fir_;
    Stack<T> sec_;
    size_t cap_;
    size_t size_;
};

void test1()
{
    Queue<int> que;
    que.push(1);
    que.push(2);
    que.push(3);

    cout << que.top() << endl;
    que.pop();
    cout << que.top() << endl;
    que.push(4);
    cout << que.top() << endl;
    que.pop();
    cout << que.top() << endl;
    que.push(6);
    que.pop();
    cout << que.top() << endl;

    que.pop();
    cout << que.top() << endl;

}

int main()
{
    test1();
    return 0;
}